using ll = long long;

ll get_eular_sum(int n) {
	vector<int> primes;
	vector<bool> st(n + 1);
	vector<ll> phi(n + 1);
	phi[1] = 1;

	for (int i = 2; i <= n; i++) {
		if (!st[i]) {
			primes.emplace_back(i);
			phi[i] = i - 1;
		}
		for (auto &j : primes) {
			int v = j * i;
			if (v > n) {
				break;
			}
			st[v] = true;
			if (i % j == 0) {
				phi[v] = phi[i] * j;
				break;
			}
			phi[v] = phi[i] * (j - 1);
		}
	}

	ll s = 0;
	for (int i = 1; i <= n; i++) {
		s += phi[i];
	}
	return s;
}